Diseño Y Análisis De Algoritmos

1 Contenido de la clase

De la triangulación de polígonos a la de conjuntos de puntos [00:00-03:49]

La clase continúa el tema de triangulaciones de la clase anterior (polígonos), pero ahora el problema es triangular un conjunto de puntos en el plano. La primera pregunta es si todo conjunto de puntos se puede triangular: siempre se pueden conectar los puntos con segmentos que no se crucen hasta que todas las regiones queden como triángulos, y el profesor lo comprueba dibujando ejemplos a mano [00:00-03:49]. También muestra una herramienta de visualización animada para dibujar y girar las configuraciones (por ejemplo, genera un pentágono con sus 5 vértices y lo gira sobre su lista de puntos) [03:49-05:08]. [parte no entendida: el nombre exacto de la herramienta y varios ejemplos numéricos de la pizarra]

La pregunta central: la triangulación de Delaunay [45:05-46:02]

La pregunta que ordena toda la clase es: ¿cómo hacer una triangulación en la que el círculo circunscrito de cada triángulo no tenga puntos dentro? [45:05-46:02]. Esa propiedad —la del círculo vacío: ningún punto del conjunto dentro del círculo que pasa por los tres vértices del triángulo— es la que define la triangulación de Delaunay. Se quiere probar que, para cualquier conjunto de puntos en posición general (sin 4 puntos cocirculares), esa triangulación existe [47:55-48:30].

Flips: convertir cualquier triangulación en una de Delaunay [23:25-24:35]

Para llegar a una triangulación de Delaunay se parte de una triangulación cualquiera y se aplican flips: si dos triángulos comparten una arista y forman un cuadrilátero convexo, se elimina esa arista y se sustituye por la otra diagonal [23:25-24:35]. Repitiendo el proceso se eliminan las aristas "ilegales" (las que hacen que el círculo circunscrito de algún triángulo contenga un punto) hasta que todos los triángulos cumplen la propiedad del círculo vacío [43:23-43:53]. El profesor pide "llevar la cuenta" del avance e introduce un peso asociado a la triangulación para controlar el proceso [26:28-26:46]. [parte no entendida: la definición precisa de ese peso y varios pasos intermedios]

La idea del paraboloide: ver la triangulación "desde abajo" [48:39-49:59]

Una de las ideas visuales más importantes es elevar los puntos a un paraboloide y observar la construcción "desde abajo": lo que se ve mirando desde la parte inferior es precisamente la triangulación de Delaunay, mientras que otras triangulaciones corresponden a la vista superior [48:39-49:59, 60:58-62:55]. El profesor insiste en "lo que se ve desde abajo" como la forma correcta de leer la figura [66:19-66:34]. [parte no entendida: la formalización completa de la elevación]

La propiedad del círculo vacío con tres puntos [63:17-65:27]

Con tres puntos se traza el círculo que pasa por ellos: dentro de ese círculo no debe haber ningún otro punto; si hubiera uno, los triángulos no podrían quedar como están y habría que rehacer la conexión [63:17-65:27]. La prueba se apoya en que, tomados tres puntos, "aquí abajo del círculo no hay nada más que los tres puntos" [69:34-69:59]. El profesor trabaja el ejemplo con puntos etiquetados (P7, P8) [43:23-43:53].

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

En esta clase no se indicaron tareas con fecha de entrega. Conviene repasar por cuenta propia:

[parte no entendida — posibles ejercicios concretos que quedaron escritos en la pizarra]

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

El profesor no citó recursos concretos en esta clase. Recursos útiles para profundizar lo explicado:

6 Glosario de términos

• Triangulación de Delaunay: triangulación de un conjunto de puntos donde el círculo circunscrito de cada triángulo no contiene ningún otro punto del conjunto.
• Círculo circunscrito: el círculo que pasa por los tres vértices de un triángulo.
• Propiedad del círculo vacío: condición de que dentro del círculo circunscrito de cada triángulo no haya puntos del conjunto.
• Flip: operación que reemplaza la arista común de dos triángulos adyacentes por la otra diagonal del cuadrilátero que forman.
• Arista ilegal: arista compartida por dos triángulos cuyo círculo circunscrito contiene un punto; debe voltearse para llegar a Delaunay.
• Posición general: en este contexto, que no haya 4 puntos cocirculares (ni 3 colineales); garantiza que la triangulación de Delaunay sea única.
• Paraboloide: superficie sobre la que se "elevan" los puntos; mirar la nube elevada desde abajo permite visualizar la triangulación de Delaunay.
• Peso: medida que el profesor propone para llevar la cuenta del avance hacia la triangulación de Delaunay [parte no entendida].

7 Mapa mental textual

• Diseño Y Análisis De Algoritmos · Clase 9
  • Triangulación de un conjunto de puntos
    • Todo conjunto de puntos se puede triangular
    • Herramienta de visualización animada para dibujar y girar configuraciones
  • Triangulación de Delaunay
    • Propiedad del círculo vacío: el círculo circunscrito de cada triángulo no contiene puntos
    • Posición general: sin 4 puntos cocirculares
    • Dentro del círculo de tres puntos no hay más que esos tres
  • Cómo se construye
    • Partir de una triangulación cualquiera
    • Flips: cambiar la diagonal común de dos triángulos
    • Eliminar aristas ilegales → triangulación de Delaunay
    • Llevar la cuenta del proceso con un peso
  • Visualización del paraboloide
    • Elevar los puntos a un paraboloide
    • Leer la triangulación "desde abajo" = Delaunay